#include "headfiles.h"

using namespace std;

void coinCombinationRecur(int total_cents, int coin_cent, int *coin_num) {
    if (total_cents < 0) {
        cout << "Error, invalid total cent num: " << total_cents << endl;
        return;
    }

    int i;
    // For quarters
    if (coin_cent == 25) {
        i = 0;
        while (25 * i <= total_cents) {
            coin_num[0] = i;
            coinCombinationRecur(total_cents - i * 25, 10, coin_num);
            ++i;
        }
    }
    else if (coin_cent == 10) {
        i = 0;
        while (10 * i <= total_cents) {
            coin_num[1] = i;
            coinCombinationRecur(total_cents - i * 10, 5, coin_num);
            ++i;
        }
    }
    else if (coin_cent == 5) {
        i = 0;
        while (5 * i <= total_cents) {
            coin_num[2] = i;
            coinCombinationRecur(total_cents - i * 5, 1, coin_num);
            ++i;
        }
    }
    else if (coin_cent == 1) {
        coin_num[3] = total_cents;
        for (i = 0; i < 4; i++) {
            cout << coin_num[i] << "\t";
        }
        cout << endl;
    }
    else {
        cout << "Incorrect coin cents: " << coin_cent << "!" << endl;
    }

    return;
}

void coinCombination(int total_cents) {
    int coin_num[4];
    coinCombinationRecur(total_cents, 25, coin_num);
}
